#include "stdafx.h"
#include "BasicTimerBase.h"
#include "BasicThreadGlobalData.h"
#include "BasicThreadTimers.h"
#include "BasicCurrentTime.h"
#include <limits.h>
#include <limits>
#include <math.h>
#include <algorithm>
#include <assert.h>

namespace BasicSkinTimer
{
	static vectorHeap& threadGlobalTimerHeap()
	{
		return GetThreadGlobalData().threadTimers().timerHeap();
	}

	class TimerHeapReference;
	class TimerHeapPointer {
	public:
		TimerHeapPointer(BasicTimerBase** pointer) : m_pointer(pointer) { }
		TimerHeapReference operator*() const;
		BasicTimerBase* operator->() const { return *m_pointer; }
	private:
		BasicTimerBase** m_pointer;
	};

	class TimerHeapReference {
	public:
		TimerHeapReference(BasicTimerBase*& reference) : m_reference(reference) { }
		operator BasicTimerBase*() const { return m_reference; }
		TimerHeapPointer operator&() const { return &m_reference; }
		TimerHeapReference& operator=(BasicTimerBase*);
		TimerHeapReference& operator=(TimerHeapReference);
	private:
		BasicTimerBase*& m_reference;
	};

	inline TimerHeapReference TimerHeapPointer::operator*() const
	{
		return *m_pointer;
	}

	inline TimerHeapReference& TimerHeapReference::operator=(BasicTimerBase* timer)
	{
		m_reference = timer;
		vectorHeap& heap = timer->timerHeap();
		if (&m_reference >= heap.data() && &m_reference < heap.data() + heap.size())
			timer->m_heapIndex = &m_reference - heap.data();
		return *this;
	}

	inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference b)
	{
		BasicTimerBase* timer = b;
		return *this = timer;
	}

	inline void swap(TimerHeapReference a, TimerHeapReference b)
	{
		BasicTimerBase* timerA = a;
		BasicTimerBase* timerB = b;

		// Invoke the assignment operator, since that takes care of updating m_heapIndex.
		a = timerB;
		b = timerA;
	}

	// ----------------

	// Class to represent iterators in the heap when calling the standard library heap algorithms.
	// Uses a custom pointer and reference type that update indices for pointers in the heap.
	class TimerHeapIterator : public iterator<random_access_iterator_tag, BasicTimerBase*, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
	public:
		explicit TimerHeapIterator(BasicTimerBase** pointer) : m_pointer(pointer) { checkConsistency(); }

		TimerHeapIterator& operator++() { checkConsistency(); ++m_pointer; checkConsistency(); return *this; }
		TimerHeapIterator operator++(int) { checkConsistency(1); return TimerHeapIterator(m_pointer++); }

		TimerHeapIterator& operator--() { checkConsistency(); --m_pointer; checkConsistency(); return *this; }
		TimerHeapIterator operator--(int) { checkConsistency(-1); return TimerHeapIterator(m_pointer--); }

		TimerHeapIterator& operator+=(ptrdiff_t i) { checkConsistency(); m_pointer += i; checkConsistency(); return *this; }
		TimerHeapIterator& operator-=(ptrdiff_t i) { checkConsistency(); m_pointer -= i; checkConsistency(); return *this; }

		TimerHeapReference operator*() const { return TimerHeapReference(*m_pointer); }
		TimerHeapReference operator[](ptrdiff_t i) const { return TimerHeapReference(m_pointer[i]); }
		BasicTimerBase* operator->() const { return *m_pointer; }

	private:
		void checkConsistency(ptrdiff_t offset = 0) const
		{
			assert(m_pointer >= threadGlobalTimerHeap().data());
			assert(m_pointer <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().size());
			//ASSERT_UNUSED(offset, m_pointer + offset >= threadGlobalTimerHeap().data());
			//  ASSERT_UNUSED(offset, m_pointer + offset <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().size());
		}

		friend bool operator==(TimerHeapIterator, TimerHeapIterator);
		friend bool operator!=(TimerHeapIterator, TimerHeapIterator);
		friend bool operator<(TimerHeapIterator, TimerHeapIterator);
		friend bool operator>(TimerHeapIterator, TimerHeapIterator);
		friend bool operator<=(TimerHeapIterator, TimerHeapIterator);
		friend bool operator>=(TimerHeapIterator, TimerHeapIterator);

		friend TimerHeapIterator operator+(TimerHeapIterator, size_t);
		friend TimerHeapIterator operator+(size_t, TimerHeapIterator);

		friend TimerHeapIterator operator-(TimerHeapIterator, size_t);
		friend ptrdiff_t operator-(TimerHeapIterator, TimerHeapIterator);

		BasicTimerBase** m_pointer;
	};

	inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer == b.m_pointer; }
	inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer != b.m_pointer; }
	inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer < b.m_pointer; }
	inline bool operator>(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer > b.m_pointer; }
	inline bool operator<=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer <= b.m_pointer; }
	inline bool operator>=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer >= b.m_pointer; }

	inline TimerHeapIterator operator+(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer + b); }
	inline TimerHeapIterator operator+(size_t a, TimerHeapIterator b) { return TimerHeapIterator(a + b.m_pointer); }

	inline TimerHeapIterator operator-(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer - b); }
	inline ptrdiff_t operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer - b.m_pointer; }
	class TimerHeapLessThanFunction {
	public:
		bool operator()(const BasicTimerBase*, const BasicTimerBase*) const;
	};

	inline bool TimerHeapLessThanFunction::operator()(const BasicTimerBase* a, const BasicTimerBase* b) const
	{
		// The comparisons below are "backwards" because the heap puts the largest 
		// element first and we want the lowest time to be the first one in the heap.
		double aFireTime = a->m_nextFireTime;
		double bFireTime = b->m_nextFireTime;

		if (bFireTime != aFireTime)
			return bFireTime < aFireTime;

		// We need to look at the difference of the insertion orders instead of comparing the two 
		// outright in case of overflow. 
		unsigned difference = a->m_heapInsertionOrder - b->m_heapInsertionOrder;
		return difference < 0x7fffffff;//std::numeric_limits<unsigned int>::max() / 2;
	}

	// ----------------

	BasicTimerBase::BasicTimerBase()
		: m_nextFireTime(0)
		, m_unalignedNextFireTime(0)
		, m_repeatInterval(0)
		, m_heapIndex(-1)
		, m_cachedThreadGlobalTimerHeap(0)
		//#ifndef NDEBUG
		//    , m_thread(currentThread())
		//#endif
	{
	}

	BasicTimerBase::~BasicTimerBase()
	{
		stop();
		assert(!inHeap());
	}

	void BasicTimerBase::start(double nextFireInterval, double repeatInterval)
	{
		//assert(m_thread == currentThread());

		m_repeatInterval = repeatInterval;
		setNextFireTime(monotonicallyIncreasingTime() + nextFireInterval);
	}

	void BasicTimerBase::stop()
	{
		//assert(m_thread == currentThread());

		m_repeatInterval = 0;
		setNextFireTime(0);

		assert(m_nextFireTime == 0);
		assert(m_repeatInterval == 0);
		assert(!inHeap());
	}

	double BasicTimerBase::nextFireInterval() const
	{
		assert(isActive());
		double current = monotonicallyIncreasingTime();
		if (m_nextFireTime < current)
			return 0;
		return m_nextFireTime - current;
	}

	inline void BasicTimerBase::checkHeapIndex() const
	{
		assert(timerHeap() == threadGlobalTimerHeap());
		assert(!timerHeap().empty());
		assert(m_heapIndex >= 0);
		assert(m_heapIndex < static_cast<int>(timerHeap().size()));
		assert(timerHeap()[m_heapIndex] == this);
	}

	inline void BasicTimerBase::checkConsistency() const
	{
		// Timers should be in the heap if and only if they have a non-zero next fire time.
		assert(inHeap() == (m_nextFireTime != 0));
		if (inHeap())
			checkHeapIndex();
	}

	void BasicTimerBase::heapDecreaseKey()
	{
		assert(m_nextFireTime != 0);
		checkHeapIndex();
		//push_heap(timerHeap().begin(),timerHeap().begin()+m_heapIndex+1, TimerHeapLessThanFunction());
		BasicTimerBase** heapData = timerHeap().data();
		push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapIndex + 1), TimerHeapLessThanFunction());
		checkHeapIndex();
	}

	inline void BasicTimerBase::heapDelete()
	{
		assert(m_nextFireTime == 0);
		heapPop();
		//   timerHeap().removeLast();
		timerHeap().erase(timerHeap().begin()+timerHeap().size()-1);
		m_heapIndex = -1;
	}

	void BasicTimerBase::heapDeleteMin()
	{
		assert(m_nextFireTime == 0);
		heapPopMin();
		//    timerHeap().removeLast();
		timerHeap().erase(timerHeap().begin()+timerHeap().size()-1);
		m_heapIndex = -1;
	}

	inline void BasicTimerBase::heapIncreaseKey()
	{
		assert(m_nextFireTime != 0);
		heapPop();
		heapDecreaseKey();
	}

	inline void BasicTimerBase::heapInsert()
	{
		assert(!inHeap());
		timerHeap().push_back(this);
		m_heapIndex = timerHeap().size() - 1;
		heapDecreaseKey();
	}

	inline void BasicTimerBase::heapPop()
	{
		// Temporarily force this timer to have the minimum key so we can pop it.
		double fireTime = m_nextFireTime;
		m_nextFireTime = -numeric_limits<double>::infinity();
		heapDecreaseKey();
		heapPopMin();
		m_nextFireTime = fireTime;
	}

	void BasicTimerBase::heapPopMin()
	{
		assert(this == timerHeap().front());
		checkHeapIndex();
		vectorHeap& heap = timerHeap();
		BasicTimerBase** heapData = heap.data();
		pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
		//pop_heap(heap.begin(),heap.end(), TimerHeapLessThanFunction());
		checkHeapIndex();
		assert(this == timerHeap().back());
	}

	static inline bool parentHeapPropertyHolds(const BasicTimerBase* current, const vector<BasicTimerBase*>& heap, unsigned currentIndex)
	{
		if (!currentIndex)
			return true;
		unsigned parentIndex = (currentIndex - 1) / 2;
		TimerHeapLessThanFunction compareHeapPosition;
		return compareHeapPosition(current, heap[parentIndex]);
	}

	static inline bool childHeapPropertyHolds(const BasicTimerBase* current, const vector<BasicTimerBase*>& heap, unsigned childIndex)
	{
		if (childIndex >= heap.size())
			return true;
		TimerHeapLessThanFunction compareHeapPosition;
		return compareHeapPosition(heap[childIndex], current);
	}

	bool BasicTimerBase::hasValidHeapPosition() const
	{
		assert(m_nextFireTime);
		if (!inHeap())
			return false;
		// Check if the heap property still holds with the new fire time. If it does we don't need to do anything.
		// This assumes that the STL heap is a standard binary heap. In an unlikely event it is not, the assertions
		// in updateHeapIfNeeded() will get hit.
		const vector<BasicTimerBase*>& heap = timerHeap();
		if (!parentHeapPropertyHolds(this, heap, m_heapIndex))
			return false;
		unsigned childIndex1 = 2 * m_heapIndex + 1;
		unsigned childIndex2 = childIndex1 + 1;
		return childHeapPropertyHolds(this, heap, childIndex1) && childHeapPropertyHolds(this, heap, childIndex2);
	}

	void BasicTimerBase::updateHeapIfNeeded(double oldTime)
	{
		if (m_nextFireTime && hasValidHeapPosition())
			return;
#ifndef NDEBUG
		int oldHeapIndex = m_heapIndex;
#endif
		if (!oldTime)
			heapInsert();
		else if (!m_nextFireTime)
			heapDelete();
		else if (m_nextFireTime < oldTime)
			heapDecreaseKey();
		else
			heapIncreaseKey();
		assert(m_heapIndex != oldHeapIndex);
		assert(!inHeap() || hasValidHeapPosition());
	}

	void BasicTimerBase::setNextFireTime(double newUnalignedTime)
	{
		//  assert(m_thread == currentThread());

		if (m_unalignedNextFireTime != newUnalignedTime)
			m_unalignedNextFireTime = newUnalignedTime;

		// Accessing thread global data is slow. Cache the heap pointer.
		if (!m_cachedThreadGlobalTimerHeap)
			m_cachedThreadGlobalTimerHeap = &threadGlobalTimerHeap();

		// Keep heap valid while changing the next-fire time.
		double oldTime = m_nextFireTime;
		double newTime = alignedFireTime(newUnalignedTime);
		if (oldTime != newTime) {
			m_nextFireTime = newTime;
			static unsigned currentHeapInsertionOrder;
			m_heapInsertionOrder = currentHeapInsertionOrder++;

			bool wasFirstTimerInHeap = m_heapIndex == 0;

			updateHeapIfNeeded(oldTime);

			bool isFirstTimerInHeap = m_heapIndex == 0;

			if (wasFirstTimerInHeap || isFirstTimerInHeap)
				GetThreadGlobalData().threadTimers().updateSharedTimer();
		}

		checkConsistency();
	}

	void BasicTimerBase::fireTimersInNestedEventLoop()
	{
		// Redirect to ThreadTimers.
		BasicThreadGlobalData().threadTimers().fireTimersInNestedEventLoop();
	}

	void BasicTimerBase::didChangeAlignmentInterval()
	{
		setNextFireTime(m_unalignedNextFireTime);
	}

	double BasicTimerBase::nextUnalignedFireInterval() const
	{
		assert(isActive());
		return max(m_unalignedNextFireTime - monotonicallyIncreasingTime(), 0.0);
	}
}